package com.zyk.leetcode;

import java.util.List;

/**
 * @author zhangsan
 * @date 2021/6/13 18:45
 */
public class C40 {

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        return null;
    }


    public static int f(int[] candidates, int target) {
        return process(candidates, 0, target);
    }

    public static int process(int[] candidates, int i, int rest) {
        if (i == candidates.length)
            return rest == 0 ? 1 : 0;
        int ways = process(candidates, i + 1, rest);
        if (candidates[i] <= rest) {
            ways += process(candidates, i + 1, rest - candidates[i]);
        }
        return ways;
    }


    // for test
    public static void main(String[] args) {
//        int[] candidates = {10, 1, 2, 7, 6, 1, 5};
//        int target = 8;
        int[] candidates = {1, 1, 1};
        int target = 2;
        System.out.println(f(candidates, target));
    }

}
